package com.lcz.suanfa.经典算法;

import org.junit.Test;

import java.util.Arrays;

/**
 * <pre>
 * <img width="128" height="110" src="https://tse3-mm.cn.bing.net/th/id/OIP-C.en-w_oH-yn2UsSRfWnOsGAHaGY?w=198&h=180&c=7&r=0&o=5&dpr=1.25&pid=1.7" alt="马刺">
 * 作者:     <a href="https://github.com/liuchuanzheng">刘传政</a>
 * 创建时间:  17:03 2022/2/21 0021
 * QQ:      1052374416
 * 电话:     18501231486
 * 描述:
 * </pre>
 */
public class 排序 {
    @Test
    public void test_冒泡排序() {
        int[] nums = {0, 4, 3, 0, 20, 11};
        冒泡排序_简单版(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 冒泡排序算法运行起来非常慢，但在概念上它是排序算法中最简单的，因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法。
     * 冒泡排序算法的基本流程是：每一轮从头开始两两比较，将较大的项放在较小项的右边，这样每轮下来保证该轮最大的数在最右边
     *
     * @param nums
     */
    public void 冒泡排序(int[] nums) {
        int temp;
        for (int maxIndex = nums.length - 1; maxIndex > 0; maxIndex--) {
            for (int i = 0; i < maxIndex; i++) {
                if (nums[i] > nums[i + 1]) {
                    temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                }
            }
        }
    }

    public void 冒泡排序_简单版(int[] nums) {
        //不考虑循环时少几次比较
        int temp;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1; j++) {
                //与后一个元素比较
                if (nums[j] > nums[j + 1]) {
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }

    @Test
    public void test_选择排序() {
        int[] nums = {0, 4, 3, 0, 6, 1};
        选择排序_简单版(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * @param nums
     */
    public void 选择排序(int[] nums) {
        int temp;
        int minIndex;
        for (int i = 0; i < nums.length; i++) {
            minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    temp = nums[minIndex];
                    nums[minIndex] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

    public void 选择排序_简单版(int[] nums) {
        //每次选择最小的
        int temp;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                //依次与所有元素比较
                if (nums[i] > nums[j]) {
                    System.out.println("调换前" + Arrays.toString(nums));
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    System.out.println("调换后" + Arrays.toString(nums));
                }
            }
        }

    }

    /**
     * 分割数组为一个基准元素和左右两半.左边都小,右边都大.并返回这个基准元素的位置
     *
     * @param array
     * @param low
     * @param high
     * @return
     */
    public static int halfFenge(int[] array, int low, int high) {
        // 取最后一个元素作为基准元素.其实选别的元素也行.这是为了计算方便
        int base = array[high];
        System.out.println("基准元素" + base);
        // 定义一个坑位,从左开始
        int kengwei = low;
        // 遍历数组中的所有元素，将比基准元素大的放在右边，比基准元素小的放在左边
        for (int i = low; i < high; i++) {
            if (array[i] <= base) {
                //每次小于基准元素,就把它放到坑位里.然后坑位+1.这样遍历完,填满的坑位都是小的,而且都在左边.
                int temp = array[i];
                array[i] = array[kengwei];
                array[kengwei] = temp;
                System.out.println("坑位:" + kengwei + "被" + i + "填入");
                kengwei++;
                System.out.println("坑位变为:" + kengwei);
                System.out.println(Arrays.toString(array));
            }
        }
        // 最后将基准元素和还没填好的坑位换.这样就是左小 基准元素 右大
        int temp = array[kengwei];
        array[kengwei] = array[high];
        array[high] = temp;
        //返回最后坑位,也就是基准元素的位置.一遍后续的递归继续调用

        System.out.println("本次左右分割完成,作用区域左" + low + "到右" + high);
        System.out.println("基准元素" + base + "坑位" + kengwei);
        System.out.println(Arrays.toString(array) + "----------------------------------------");
        return kengwei;
    }

    //https://zhuanlan.zhihu.com/p/373348669
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 获取分割后的基准元素位置
            int basePosition = halfFenge(array, low, high);
            // 左子数组递归调用
            quickSort(array, low, basePosition - 1);
            // 右子数组递归调用
            quickSort(array, basePosition + 1, high);
        }
    }

    @Test
    public void 快速排序() {
        int[] array = {6, 72, 113, 11, 23, 55, 2, 20};
        quickSort(array, 0, array.length - 1);
        System.out.println("排序后的结果");
        System.out.println(Arrays.toString(array));
    }

}
